home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph / _g_misc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  2.8 KB  |  154 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _g_misc.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/graph.h>
  17. #include <LEDA/ugraph.h>
  18.  
  19.  
  20.  
  21.  
  22. node_array<int>* num_ptr;
  23.   
  24. int epe_source_num(const edge& e) { return (*num_ptr)[source(e)]; }
  25. int epe_target_num(const edge& e) { return (*num_ptr)[target(e)]; }
  26.  
  27.  
  28. bool Is_Simple(graph& G)  
  29. { 
  30.   // return true iff G is simple, i.e, has no parallel edges
  31.  
  32.   list<edge>el= G.all_edges();
  33.   node v;
  34.   
  35.   edge e;
  36.   int n= 0;
  37.   
  38.   node_array<int> num(G);
  39.   forall_nodes(v,G) num[v]= n++;
  40.   
  41.   num_ptr= #
  42.   
  43.   el.bucket_sort(0,n-1,&epe_source_num);
  44.   el.bucket_sort(0,n-1,&epe_target_num);
  45.   
  46.   int i= -1;
  47.   int j= -1;
  48.   
  49.   forall(e,el)
  50.   { if(j==num[source(e)]&&i==num[target(e)])
  51.     return false;
  52.     else
  53.     { j= num[source(e)];
  54.       i= num[target(e)];
  55.     }
  56.   }
  57.   return true;
  58.   
  59. }
  60.   
  61.   
  62.   
  63.  
  64. void Make_Simple(graph& G)
  65. { 
  66.   //use bucket sort to find and eliminate parallel edges
  67.   
  68.   list<edge> el = G.all_edges();
  69.   node v;
  70.   edge e;
  71.   int  n = 0;
  72.  
  73.   node_array<int> num(G);
  74.   forall_nodes(v,G) num[v] = n++;
  75.   
  76.   num_ptr = #
  77.  
  78.   el.bucket_sort(0,n-1,&epe_source_num);
  79.   el.bucket_sort(0,n-1,&epe_target_num);
  80.   
  81.   int i = -1;
  82.   int j = -1; 
  83.   forall(e,el)  
  84.     { if (j==num[source(e)] && i==num[target(e)]) 
  85.         G.del_edge(e);
  86.       else 
  87.         { j=num[source(e)];
  88.           i=num[target(e)];
  89.          }
  90.      }
  91.   
  92.  }
  93.  
  94.  
  95.  
  96.  
  97. static int edge_ord1(const edge& e) { return index(source(e)); }
  98. static int edge_ord2(const edge& e) { return index(target(e)); }
  99.  
  100. bool Is_Bidirected(const graph& G, edge_array<edge>& reversal)     
  101. {
  102.  // computes for every edge e = (v,w) in G its reversal reversal[e] = (w,v)
  103.  // in G ( nil if not present). Returns true if every edge has a
  104.  // reversal and false otherwise.
  105.  
  106.   int n = G.max_node_index();
  107.   int count = 0;
  108.  
  109.   edge e,r;
  110.  
  111.   forall_edges(e,G) reversal[e] = 0;
  112.  
  113.   list<edge> El = G.all_edges();
  114.   El.bucket_sort(0,n,&edge_ord2);
  115.   El.bucket_sort(0,n,&edge_ord1);
  116.   
  117.   list<edge> El1 = G.all_edges();
  118.   El1.bucket_sort(0,n,&edge_ord1);
  119.   El1.bucket_sort(0,n,&edge_ord2);
  120.  
  121.  
  122.   // merge El and El1 to find corresponding edges
  123.  
  124.   while (! El.empty() && ! El1.empty())
  125.   { e = El.head();
  126.     r = El1.head();
  127.  
  128.     if (target(r) == source(e))
  129.       if (source(r) == target(e))
  130.          { reversal[e] = r;
  131.            El1.pop();
  132.            El.pop();
  133.            count++;
  134.           }
  135.       else
  136.          if (index(source(r)) < index(target(e)))
  137.              El1.pop();
  138.          else
  139.              El.pop();
  140.  
  141.     else
  142.       if (index(target(r)) < index(source(e)))
  143.           El1.pop();
  144.       else
  145.           El.pop();
  146.  
  147.     }
  148.  
  149.   return (count == G.number_of_edges()) ? true : false;
  150.  
  151. }
  152.  
  153.  
  154.